10.6 KB · ⇊ 7 parts · ⤓ Micron 10.6 KB · ⤓ HTML 44.1 KB

top

La Classification double ou « Biclustering » est une technique d'exploration de données non-supervisée permettant de segmenter simultanément les lignes et les colonnes d'une matrice. Plus formellementcite-ref-1[1], la définition de la classification double peut s'exprimer de la manière suivante (pour le type de classification par colonne) :

soit

E

{\displaystyle \mathrm {E} }

une matrice

M

×

×

N

{\displaystyle \mathrm {M} \times \mathrm {N} }

, soient

I

⊆

⊆

M

,

J

⊆

⊆

N

{\displaystyle \mathrm {I} \subseteq \mathrm {M} {\text{ , }}J\subseteq \mathrm {N} }

, alors

E

I

J

{\displaystyle \mathrm {E} _{IJ}}

est appelé

«

bicluster

»

de

E

{\displaystyle \mathrm {E} }

lorsque

E

i

1

,

j

=

E

i

2

,

j

=

.

.

=

E

i

m

,

j

{\displaystyle \mathrm {E} _{i_{1},j}=\mathrm {E} _{i_{2},j}=..=\mathrm {E} _{i_{m},j}}

pour tout

j

∈

∈

J

et

(

i

1

,

i

2

,

.

.

.

i

m

)

∈

∈

M

{\displaystyle j\in J{\text{ et }}(i_{1},i_{2},...i_{m})\in \mathrm {M} }

• Application

• Types

• Algorithmes

• Articles connexes

• Notes et références

Le « biclustering » a été utilisé massivement en biologiecite-ref-2[2] - par exemple dans l'analyse de l'expression génétique par Yizong Cheng et George M. Churchcite-ref-3[3] cite-ref-4[4] -, mais aussi dans d'autres domaines tels que la compression d'image de synthèsecite-ref-5[5], l'analyse médicale - par exemple pour l'étude des traitements de l'épilepsiecite-ref-6[6] par stimulation vagale, la caractérisation d'émetteurs de pourriels (« spam »)cite-ref-7[7], l'analyse du mouvementcite-ref-8[8], l'analyse des termes publicitaires sur internetcite-ref-9[9], ...

Dans les différents algorithmes qui utilisent la classification double, on trouve différents types de bicluster :

• « Bi-cluster » à valeurs constantes (a),

• « Bi-cluster » à valeurs constantes en lignes (b) ou en colonnes (c),

• « Bi-cluster » à valeurs cohérentes (d, e).

En d) la notion d'additivité se comprend comme ceci : + 3 , − − 1 , + 2 , − − 3 {\displaystyle +3,-1,+2,-3} en colonnes, + 3 , + 1 , − − 5 , + 1 , 5 {\displaystyle +3,+1,-5,+1,5} en lignes; en e) le motif est 1 2 , ∗ ∗ 4 , 1 10 , ∗ ∗ 4 {\displaystyle {\frac {1}{2}},*4,{\frac {1}{10}},*4} en colonnes et ∗ ∗ 2 , ∗ ∗ 1.5 , 4 3 , 5 4 {\displaystyle *2,*1.5,{\frac {4}{3}},{\frac {5}{4}}} .

Le but des algorithmes de classification double est de trouver, s'il existe, le plus grand « bi-cluster » contenu dans une matrice, en maximisant une fonction objectif. On peut prendre comme fonction, avec les notations adoptées ci-dessus :

f

1

=

|

I

|

+

|

J

|

{\displaystyle f_{1}=\left|\mathrm {I} \right|+\left|J\right|}

ou

f

2

=

|

I

|

∗

∗

|

J

|

{\displaystyle f_{2}=\left|\mathrm {I} \right|*\left|J\right|}

De nombreux algorithmes ont été développés notamment par la bio-informatique, dont : « Block clustering », CTWC (« Coupled Two-Way Clustering ») , ITWC (« Interrelated Two-Way Clustering »), δ-bicluster, δ-pCluster, δ-pattern, FLOC, OPC, « Plaid Model », OPSMs (« Order-preserving submatrixes »), Gibbs, SAMBA (« Statistical-Algorithmic Method for Bicluster Analysis »)cite-ref-11[11], RoBA (« Robust Biclustering Algorithm »), « Crossing Minimization »cite-ref-ahsan-12-0[12] , cMonkeycite-ref-13[13], PRMs, DCC, LEB (« Localize and Extract Biclusters »), QUBIC (« QUalitative BIClustering »), BCCA (« Bi-Correlation Clustering Algorithm »), FABIA (« Factor Analysis for Bicluster Acquisition »)cite-ref-14[14]. Certains de ces algorithmes ont été comparés par Doruk Bozda, Ashwin S. Kumar et Umit V. Catalyurekcite-ref-15[15] en termes de type de motifs recherchés.

Le package « biclust »cite-ref-16[16] propose un ensemble d'outils pour la classification double dans le logiciel R.

• Classification

• Classification automatique

• Segmentation (sciences humaines)

(en)

Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé

«

Biclustering

»

(

voir la liste des auteurs

)

.

cite-note-11. ↑ Tran Trang, Nguyen Cam Chi, Hoang Ngoc Minh,Bi-clustering des données de biopuces par les arbres pondérés de plus long préfixe - Chapitre 1 Introduction

cite-note-22. ↑ Sara C. Madeira, Arlindo L. Oliveira,Biclustering Biological Data Analysis

cite-note-33. ↑ y-church-gm2000cheng-y-church-gm2000(en) Cheng Y, Church GM, « Biclustering of expression data », Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology,‎ 2000, p. 93–103

cite-note-44. ↑ Yizong Cheng, George M. Church Biclustering of Expression Data

cite-note-55. ↑ Xin Sun, Qiming Hou,Zhong Ren, Kun Zhou, Baining Guo,Radiance Transfer Biclustering for Real-time All-frequency Bi-scale Rendering

cite-note-66. ↑ Stanislav Busygin,Nikita Boyko, Panos M. Pardalos,Michael Bewernitz, Georges Ghacibeh,Biclustering EEG data from epileptic patients treated with vagus nerve stimulation

cite-note-77. ↑ Kevin S. Xu, Mark Kliger, Alfred O. Hero III, Identifying Spammers by Their Resource Usage Patterns

cite-note-88. ↑ Keren Erez, Jacob Goldberger, Ronen Sosnik, Moshe Shemesh, Susan Rothstein,Moshe Abeles, Analyzing Movement Trajectories Using a Markov Bi-Clustering Method

cite-note-99. ↑ Dmitry I. Ignatov, Concept-based Biclustering for Internet Advertisement

cite-note-101. Stefano Lonardi, Qiaofeng Yang, Wojciech Szpankowski,Finding biclusters by random projections

cite-note-1111. ↑ a-sharan-r-kupiec-m-and-sahmir-r2004tanay-a-sharan-r-kupiec-m-and-sahmir-r2004(en) Tanay A, Sharan R, Kupiec M and Sahmir R, « Revealing modularity and organization in the yeast molecular network by integrated analysis of highly heterogeneous genomewide data », Proc Natl Acad Sci USA, vol. 101, no 9,‎ 2004, p. 2981-2986 (PMID 16749936, PMCID 14973197, DOI 10.1073/pnas.0308661100)

cite-note-ahsan-1212. ↑ Ahsan Abdullah, Data Mining Using the Crossing Minimization Paradigm

cite-note-1313. ↑ dj-baliga-ns-bonneau-r2006reiss-dj-baliga-ns-bonneau-r2006(en) Reiss DJ, Baliga NS, Bonneau R, « Integrated biclustering of heterogeneous genome-wide datasets for the inference of global regulatory networks », BMC Bioinformatics, vol. 2, no 7,‎ 2006, p. 280–302 (PMID 16749936, PMCID 1502140, DOI 10.1186/1471-2105-7-280)

cite-note-1414. ↑ s-bodenhofer-u-heusel-m-mayr-a-mitterecker-a-kasim-a-khamiakova-t-van-sanden-s-lin-d-talloen-w-bijnens-l-gohlmann-hwh-shkedy-z-clevert-da2010hochreiter-s-bodenhofer-u-heusel-m-mayr-a-mitterecker-a-kasim-a-khamiakova-t-van-sanden-s-lin-d-talloen-w-bijnens-l-gohlmann-hwh-shkedy-z-clevert-da2010(en) Hochreiter S, Bodenhofer U, Heusel M, Mayr A, Mitterecker A, Kasim A, Khamiakova T, Van Sanden S, Lin D, Talloen W, Bijnens L, Gohlmann HWH, Shkedy Z, Clevert DA, « FABIA: factor analysis for bicluster acquisition », Bioinformatics, vol. 26, no 12,‎ 2010, p. 1520–1527 (PMID 20418340, PMCID 2881408, DOI 10.1093/bioinformatics/btq227)

cite-note-1515. ↑ Doruk Bozda, Ashwin S. Kumar et Umit V. Catalyurek, Comparative Analysis of Biclustering Algorithms

cite-note-1616. ↑ Sebastian Kaiser, Friedrich Leisch, A Toolbox for Bicluster Analysis in R

• Portail de l’informatique

• Portail des probabilités et de la statistique

• Portail de l'informatique théorique